#include<bits/stdc++.h>
using namespace std;
struct dd{
    int w,v;
}bag[1001][1001];
int bag_len,len[1001],pos[1001],f[1001][1001];
int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1,w,v,group;i<=n;i++){
        scanf("%d%d%d",&w,&v,&group);
        if(!pos[group])pos[group]=++bag_len;
        bag[pos[group]][++len[pos[group]]]=(dd){w,v};
    }
    for(int i=1;i<=bag_len;i++){
        for(int k=1;k<=m;k++)f[i][k]=f[i-1][k];
        for(int j=1;j<=len[i];j++)
            for(int k=bag[i][j].w;k<=m;k++)
                f[i][k]=max(f[i-1][k-bag[i][j].w]+bag[i][j].v,f[i][k]);
    }
    printf("%d",f[bag_len][m]);
}